// 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
// 其实就是有序数组，从后往前的累加，有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，
// 对于二叉搜索树来说，按照逆序累加，即右中左，累加
// 思路，递归，中序遍历
function convertBST(root) {
    let preVal = 0
    function dfs(root) {
        if (!root) {
            return 0
        }
        dfs(root.right)
        root.val += preVal
        preVal = root.val
        dfs(root.left)
    }
    dfs(root)
    return root
}

// 思路2， 迭代
function convertBST2(root) {
    let preVal = 0
    let stack = []
    let cur = root
    while (stack.length || cur) {
        if (cur) {
            stack.push(cur)
            cur = cur.right
        } else {
            let node = stack.pop()
            node.val += preVal
            preVal = node.val
            cur = node.left
        }
    }
    return root
}

let root = {
    val: 5,
    left: {
        val: 2
    },
    right: {
        val: 13
    }
}

// console.log(convertBST(root))
console.log(convertBST2(root))